package com.wfm.alg;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import org.junit.Test;

// 把root放进队列
// 记录当前队列的节点个数cnt，依次从队列中取出节点，直到取出全部cnt为止，将每次取出的cur【值放入临时列表】，【子节点放入队列】
public class P广度优先搜索 {

    //====================矩阵===================
    public List<List<Integer>> levelOrderMatrix(int[][] root){
        List<List<Integer>> bfs = bfs(root, 0, 0);
        return bfs;
    }
    public List<List<Integer>> bfs(int[][] grid,int i,int j){
        // 定义res、quequ，入队列，visited看情况定(需要注意的是visited改变值的时候应该在加子节点的时候，而不是保存val的时候，否则会重复)
        List<List<Integer>> res = new ArrayList<>();
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{i,j});
        visited[i][j]=true;
        // 2 判断队列
        while (!queue.isEmpty()){
            // 2.1 定义size tmp等
            int size = queue.size();
            List<Integer> tmp = new ArrayList<>();
            // 2.2 遍历当前层节点个数
            for (int k = 0; k < size; k++) {
                int[] cur = queue.poll();
                // 2.2.1 对cur做操作
                i=cur[0];j=cur[1];
                if(i>=0&&i<grid.length&&j>=0&&j<grid[0].length){
                    tmp.add(grid[i][j]);
                }
                // 2.2.2 把cur的相邻节点加入队列
                int[][] direct = {{0,1},{0,-1},{1,0},{-1,0}};
                for(int[] d:direct){
                    i=i+d[0];
                    j=j+d[1];
                    if(i>=0&&i<grid.length&&j>=0&&j<grid[0].length&&visited[i][j]==false){
                        queue.offer(new int[]{i,j});
                        visited[i][j]=true;
                    }
                }
            }
            // 2.3 res记录当前层结果集tmp
            res.add(tmp);
        }
        return res;
    }

    @Test
    public void test1(){
        int[][] ints = {{1, 2, 3, 4},
                        {5, 6, 7, 8},
                        {9, 10, 11, 12}};
        List<List<Integer>> lists = levelOrderMatrix(ints);
        System.out.println(lists);
    }

    // ====================N叉树==================
    class Node{
        public int val;
        public List<Node> children;
        public Node(){}
        public Node(int val){
            this.val=val;
        }
        public Node(int val,List<Node> children){
            this.val=val;
            this.children=children;
        }
    }
    // 把root放进队列
    // 记录当前队列的节点个数cnt，依次从队列中取出节点，直到取出全部cnt为止，将每次取出的cur【值放入临时列表】，【子节点放入队列】
    public List<List<Integer>> levelOrderNTree(Node root){
        if(root==null) return new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            List<Integer> tmp = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node cur = queue.poll();
                tmp.add(cur.val);

                if(cur.children!=null){
                    for (int j = 0; j < cur.children.size(); j++) {
                        queue.offer(cur.children.get(j));
                    }
                }
            }
            res.add(tmp);
        }
        return res;
    }
    @Test
    public void test(){
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        List<Node> level1= Arrays.asList(node3,node2,node4);
        List<Node> level2= Arrays.asList(node5,node6);
        node1.children=level1;
        node3.children=level2;

        List<List<Integer>> lists = levelOrderNTree(node1);
        System.out.println(lists);
    }
}
